package com.LeeCode;

/**
 * 阶乘函数后 K 个零
 */

public class Code793 {
    public static void main(String[] args) {
        System.out.println(new Code793().preimageSizeFZF(15));
    }

    public int preimageSizeFZF(int k) {
        return (int) (help(k + 1) - help(k));
    }

    public long help(int k) {
        long right = 5L * k;
        long left = 0;
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (zeta(mid) >= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return left;
    }

    public long zeta(long x) {
        long res = 0;
        while (x != 0) {
            res += x / 5;
            x /= 5;
        }
        return res;
    }
}
